#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node_s {
	int data;
	int bf;
	struct node_s *left;
	struct node_s *right;
} node_t;

inline void cal_bf(node_t *p)
{
	int l = 0, r = 0;
	if (p->left)
		l = p->left->bf;
	if (p->right)
		r = p->right->bf;
	p->bf = r - l;
}

void rotate_left(node_t *p, node_t *gp, node_t **root)
{
	node_t *r = p->right;

	if (NULL == gp) {
		*root = r;
	} else {
		if (p == gp->left)
			gp->left = r;
		else
			gp->right = r;
	}

	p->right = r->left;
	r->left = p;
}

void rotate_right(node_t *p, node_t *gp, node_t **root)
{
	node_t *l = p->left;

	if (NULL == gp) {
		*root = l;
	} else {
		if (p == gp->left)
			gp->left = l;
		else
			gp->right = l;
	}

	p->left = l->right;
	l->right = p;
}

void adjust(node_t *ggp, node_t *gp, node_t **root)
{
	node_t *pos = NULL;
	
	if (gp->bf == -2) {
		pos = gp->left;
		if (gp->left->bf == -1) {
			printf("gp:%d:son:%d:gs:%d\n", gp->data, gp->left->data, gp->left->left->data);
			rotate_right(gp, ggp, root);
		} else if (gp->left->bf == 1) {
			printf("gp:%d:son:%d:gs:%d\n", gp->data, gp->left->data, gp->left->right->data);
			rotate_left(gp->left, gp, root);
			rotate_right(gp, ggp, root);
		} else 
			printf("error\n");
	} else if (gp->bf == 2) {
		pos = gp->right;
		if (gp->right->bf == 1) {
			printf("gp:%d:son:%d:gs:%d\n", gp->data, gp->right->data, gp->right->right->data);
			rotate_left(gp, ggp, root);
		} else if (gp->right->bf == -1) {
			printf("gp:%d:son:%d:gs:%d\n", gp->data, gp->right->data, gp->right->left->data);
			rotate_right(gp->right, gp, root);
			rotate_left(gp, ggp, root);
		} else 
			printf("error\n");
	} else 
		printf("error\n");
		
	cal_bf(pos->left);
	cal_bf(pos->right);
	cal_bf(pos);

	printf("pos::data:%d:bf:%d\n", pos->data, pos->bf);
	printf("left::data:%d:bf:%d\n", pos->left->data, pos->left->bf);
	printf("right::data:%d:bf:%d\n", pos->right->data, pos->right->bf);
}

void insert_tree(node_t **root, long data)
{
	node_t *new, *p, *gp = NULL, *ggp = NULL, *parent = NULL;

	new = (node_t *)malloc(sizeof(node_t));
	if (new == NULL) {
		printf("malloc for node failed\n");
		return;
	}
	memset(new, 0, sizeof(node_t));
	new->data = data;

	if (NULL == *root) {
		*root = new;
		return;
	}

	p = *root; 
	while(1) {
		if (data >= p->data) {
			if (p->right) {
				parent = p;
				p = p->right;
			} else {
				p->right = new;
				break;
			}
		} else {
			if (p->left) {
				parent = p;
				p = p->left;
			} else {
				p->left = new;
				break;
			}
		}
	}
	if (gp)
		adjust(ggp, gp, root);
}

void create_tree(node_t **root)
{
	int i, n, data[] = {6, 5, 4, 3, 2, 1};

	n = sizeof(data) / sizeof(int);
	for (i = 0; i < n; i ++) {
		printf("insert::i:%d:data:%d\n", i, data[i]);
		insert_tree(root, data[i]);
	}
}

void pre_scan_tree(node_t *node)
{
	printf("%d\t", node->data);
	if (node->left)
		pre_scan_tree(node->left);
	if(node->right)
		pre_scan_tree(node->right);
}

void mid_scan_tree(node_t *node)
{
	if (node->left)
		mid_scan_tree(node->left);
	printf("%d\t", node->data);
	if(node->right)
		mid_scan_tree(node->right);
}

#define MAX 64

typedef struct {
	node_t *arr[MAX];
	int start;
	int end;
} queue_t;
queue_t queue[1];

void  init_queue(queue_t *queue)
{
	memset(queue->arr, 0, sizeof(node_t *) * MAX);
	queue->start = queue->end = 0;
}

int enter_queue(queue_t *q, node_t *new)
{
	if (q->end == MAX)
		return -1;
	q->arr[q->end] = new;
	q->end ++;

	return 0;
}

node_t* out_queue(queue_t *q)
{
	node_t *ret = NULL;

	if (q->start != q->end) {
		ret = q->arr[q->start];
		q->start++;
	}
	
	return ret;
}

void tier_scan_tree(node_t *root)
{
	queue_t queue[1];
	node_t *node;

	init_queue(queue);
	enter_queue(queue, root);
	node = out_queue(queue);
	while (node != NULL) {
		printf("%d\t", node->data);
		if(node->left)
			enter_queue(queue, node->left);
		if(node->right)
			enter_queue(queue, node->right);

		node = out_queue(queue);
	}
	
}

int main()
{
	node_t *root = NULL;

	create_tree(&root);
	printf("\nprv_scan_tree:");
	pre_scan_tree(root);
	printf("\nmid_scan_tree:");
	mid_scan_tree(root);

	printf("\ntier_scan_tree:");
	tier_scan_tree(root);
	return 0;
}

